package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution_50 {
    public double myPow(double x, int n) {
        double base = x, rst = 1.0, temp = 1.0;
        if (n == Integer.MIN_VALUE) {
            n += 1;
            temp /= x;
        }
        int count = Math.abs(n), m = 1;
        List<Integer> list = new ArrayList<>();
        Map<Integer, Double> map = new HashMap<>();
        while (count > 0) {
            double add = 1.0;
            if (count >= m) {
                map.put(m, base);
                list.add(m);
                add = base;
                count -= m;
                base *= base;
                m <<= 1;
            } else {
                for (int i = list.size() - 1; i >= 0; i--) {
                    if (count >= list.get(i)) {
                        add = map.get(list.get(i));
                        count -= list.get(i);
                        break;
                    }
                }
            }
            rst *= add;
        }
        return n >= 0 ? rst : temp / rst;
    }

    public static void main(String[] args) {
        Solution_50 model = new Solution_50();
        System.out.println(model.myPow(2, -10));
//        System.out.println(model.myPow(1, 2));
    }
}
